//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// extendible_hash_table.cpp
//
// Identification: src/container/hash/extendible_hash_table.cpp
//
// Copyright (c) 2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <cassert>
#include <cstdlib>
#include <functional>
#include <list>
#include <utility>

#include "container/hash/extendible_hash_table.h"
#include "storage/page/page.h"

namespace bustub {

template <typename K, typename V>
ExtendibleHashTable<K, V>::ExtendibleHashTable(size_t bucket_size)
    : global_depth_(0), bucket_size_(bucket_size), num_buckets_(1) {
      this->dir_.push_back(std::make_shared<Bucket>(bucket_size));
    }

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t {
  int mask = (1 << global_depth_) - 1;
  return std::hash<K>()(key) & mask;
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetGlobalDepth() const -> int {
  std::scoped_lock<std::mutex> lock(latch_);
  return GetGlobalDepthInternal();
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetGlobalDepthInternal() const -> int {
  return global_depth_;
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetLocalDepth(int dir_index) const -> int {
  std::scoped_lock<std::mutex> lock(latch_);
  return GetLocalDepthInternal(dir_index);
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetLocalDepthInternal(int dir_index) const -> int {
  return dir_[dir_index]->GetDepth();
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetNumBuckets() const -> int {
  std::scoped_lock<std::mutex> lock(latch_);
  return GetNumBucketsInternal();
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::GetNumBucketsInternal() const -> int {
  return num_buckets_;
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Find(const K &key, V &value) -> bool {
  int idx = long(key)%this->dir_.size();
  return this->dir_[idx]->Find(key,value);
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Remove(const K &key) -> bool {
  std::scoped_lock<std::mutex> lock(latch_);
  int idx = (long)key%this->dir_.size();
  return this->dir_[idx]->Remove(key);
  // UNREACHABLE("not implemented");
}

template <typename K, typename V>
void ExtendibleHashTable<K, V>::Insert(const K &key, const V &value) {
  std::scoped_lock<std::mutex> lock(latch_);
  uint64_t idx=0;
  if(this->dir_.size()>0)
    idx = long(key)%this->dir_.size();
  
  while(!this->dir_[idx]->Insert(key,value)){//插入失败
    int new_len = this->dir_.size()*2;
    std::vector<std::shared_ptr<Bucket>> new_dir_(new_len);
    this->bucket_size_++;
    this->global_depth_++;
    for(std::shared_ptr<Bucket> e : this->dir_){//遍历Bucket
      if(!e)
        continue;
      for(auto item : e->GetItems()){//遍历Bucket中的，pair{k,v}
        
        idx = long(item.first)%new_len; //this->hashfunction.GetHash(item.first)
        if(!new_dir_[idx]){
          new_dir_[idx] = std::make_shared<Bucket>(this->bucket_size_);//TODO
        }
        new_dir_[idx]->Insert(item.first,item.second);
      }
    }
    this->dir_ = std::move(new_dir_);//将之前没有插入成功的插入
    idx = long(key)%this->dir_.size(); //this->hashfunction.GetHash(key)
    
  }


}

//===--------------------------------------------------------------------===//
// Bucket
//===--------------------------------------------------------------------===//
template <typename K, typename V>
ExtendibleHashTable<K, V>::Bucket::Bucket(size_t array_size, int depth) : size_(array_size), depth_(depth) {}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Bucket::Find(const K &key, V &value) -> bool {
  for(auto e : this->list_){
    if(e.first==key){
      value=e.second;
      return true;
    }
  }
  return false;
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Bucket::Remove(const K &key) -> bool {
  auto e = this->list_.begin();
  for(;e!=this->list_.end();e++){
    if((*e).first==key)
      break;
  }
  if(e==this->list_.end())
    return false;
  this->list_.erase(e);
  return true;
  // UNREACHABLE("not implemented");
}

template <typename K, typename V>
auto ExtendibleHashTable<K, V>::Bucket::Insert(const K &key, const V &value) -> bool {
  if(this->depth_==(int)this->size_)
    return false;
  for(auto &e:this->list_){
    if(e.first==key){
      e.second=value;
      return true;
    }      
  }
  this->list_.push_back({key,value});
  this->IncrementDepth();
  return true;
}

template class ExtendibleHashTable<page_id_t, Page *>;
template class ExtendibleHashTable<Page *, std::list<Page *>::iterator>;
template class ExtendibleHashTable<int, int>;
// test purpose
template class ExtendibleHashTable<int, std::string>;
template class ExtendibleHashTable<int, std::list<int>::iterator>;

}  // namespace bustub
